//颜色分类
class Solution {
public:
    void sortColors(vector<int>& nums) 
    {
        int n = nums.size();
        int left = -1, right = n;
        for(int i = 0; i < right;)
        {
            if(nums[i] == 0)
                swap(nums[++left],nums[i++]);
            else if(nums[i] == 1)
                i++;
            else
                swap(nums[--right],nums[i]);
        }
            
    }
};
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) 
    {
        //种一棵随机数种子
        srand(time(nullptr));
        sort(nums, 0, nums.size() - 1);
        return nums;
    }

    //快排
    void sort(vector<int> &nums, int begin, int end)
    {
        if(begin >= end)
            return;
        int key = getRando(nums,begin,end);

        int i = begin, left = begin - 1, right = end + 1;
        while(i < right)
        {
            //三路划分
            if(nums[i] < key) 
                swap(nums[++left], nums[i++]);
            else if(nums[i] == key)
                i++;
            else
                swap(nums[--right],nums[i]);
        }
        //    > key        == key         < key
        //[begin,left][left+1,right-1][right,end]
        sort(nums,begin,left);
        sort(nums,right, end);
    }

    //提供随机数来当key
    int getRando(vector<int> &nums, int begin, int end)
    {
        int res = rand();
        return nums[res % (end - begin + 1) + begin];
    }
 

};